//746 使用最小花费爬楼梯
// class Solution {
// public:
//     int minCostClimbingStairs(vector<int>& cost) {
//         //1.创建dp表
//         //2.初始化
//         //3.填表
//         //4.返回值
//         int n = cost.size();
//         vector<int> money(n+1);
//         for(int i=2;i<money.size();i++)
//             money[i]=min(money[i-1]+cost[i-1],money[i-2]+cost[i-2]);
        
//         return money[n];
//     }
// };

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int n = cost.size();
        vector<int> money(n);
        money[n-1]=cost[n-1];
        money[n-2]=cost[n-2];
        for(int i=n-3;i>=0;i--)
            money[i]=min(money[i+1]+cost[i],money[i+2]+cost[i]);
        
        return min(money[0],money[1]);
    }
};

//三步问题
class Solution {
public:
    int waysToStep(int n) {
        //创建dp表
        //初始化
        //填表
        //返回值
        const int MOD=1e9+7;
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;

        int a=1,b=2,c=4,d=0;
        for(int i=4;i<=n;i++)
        {
            d=((a+b)%MOD+c)%MOD;
            //开始滚动
            a=b;
            b=c;
            c=d;
        }
        return d;
    }
};